package leetcode;

import java.util.LinkedList;
import java.util.List;

/**
 * Created by Ghost on 2014/11/17 0017.
 */
class Interval {
    int start;
    int end;

    Interval() {
        start = 0;
        end = 0;
    }

    Interval(int s, int e) {
        start = s;
        end = e;
    }
}

public class Insert_Interval {
    public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
        int max = 0;

        if(intervals==null || intervals.size()==0){
            LinkedList<Interval> list = new LinkedList<Interval>();
            list.add(newInterval);
            return list;
        }
        LinkedList<Interval> list = new LinkedList<Interval>();
        boolean flag = false;
        for(Interval interval:intervals){
            if(newInterval.start<interval.start){
                list.add(newInterval);
                if(max<newInterval.end)
                    max = newInterval.end;
                list.add(interval);
                if(max<interval.end)
                    max = interval.end;
                flag = true;
            }
            else{
                list.add(interval);
                if(max<interval.end)
                    max = interval.end;
            }
        }
        if(!flag){
            list.add(newInterval);
            if(max<newInterval.end)
                max = newInterval.end;
        }


        int sub = list.getFirst().start;
        int total = max - sub+1;
        int[][] S = new int[total][2];
        for(Interval interval:list){
            S[interval.start-sub][0] +=1;
            S[interval.end-sub][1]-=1;
        }

        LinkedList<Interval> rst = new LinkedList<Interval>();
        int flag2 = 0;
        int start = sub;
        int end;
        boolean fuweiStart = true;
        boolean fuweiEnd = true;
        for(int i=0;i<S.length;i++){
            flag2+=S[i][0];
            if(flag2>0 && fuweiStart){
                start = i+sub;
                fuweiStart=false;
                fuweiEnd = true;
            }
            flag2+=S[i][1];

            if(flag2==0 && fuweiEnd){
                end = i+sub;
                rst.add(new Interval(start,end));
                fuweiEnd = false;
                fuweiStart = true;
            }
        }
        return rst;
    }

    public static void main(String[] args){
        Insert_Interval insert_interval = new Insert_Interval();
        Interval interval1 = new Interval(1,5);
        /*Interval interval2 = new Interval(3,5);
        Interval interval3 = new Interval(6,7);
        Interval interval4 = new Interval(8,10);
        Interval interval5 = new Interval(12,16);
*/

        Interval interval7 = new Interval(2,7);


        List<Interval> list = new LinkedList<Interval>();
        list.add(interval1);
        List<Interval> rst = insert_interval.insert(list,interval7);

        for(Interval interval: rst){
            System.out.println(interval.start+" "+interval.end);
        }
    }
}
